package  main.java.leetcode.editor.cn;
//2023-05-08 10:19:57
//给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，其中下标在 (r, c) 处的整数表示： 
//
// 
// 如果 grid[r][c] = 0 ，那么它是一块 陆地 。 
// 如果 grid[r][c] > 0 ，那么它是一块 水域 ，且包含 grid[r][c] 条鱼。 
// 
//
// 一位渔夫可以从任意 水域 格子 (r, c) 出发，然后执行以下操作任意次： 
//
// 
// 捕捞格子 (r, c) 处所有的鱼，或者 
// 移动到相邻的 水域 格子。 
// 
//
// 请你返回渔夫最优策略下， 最多 可以捕捞多少条鱼。如果没有水域格子，请你返回 0 。 
//
// 格子 (r, c) 相邻 的格子为 (r, c + 1) ，(r, c - 1) ，(r + 1, c) 和 (r - 1, c) ，前提是相邻格子在网格
//图内。 
//
// 
//
// 示例 1： 
//
// 
//
// 输入：grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
//输出：7
//解释：渔夫可以从格子 (1,3) 出发，捕捞 3 条鱼，然后移动到格子 (2,3) ，捕捞 4 条鱼。
// 
//
// 示例 2： 
//
// 
//
// 输入：grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
//输出：1
//解释：渔夫可以从格子 (0,0) 或者 (3,3) ，捕捞 1 条鱼。
// 
//
// 
//
// 提示： 
//
// 
// m == grid.length 
// n == grid[i].length 
// 1 <= m, n <= 10 
// 0 <= grid[i][j] <= 10 
// 
// Related Topics 深度优先搜索 广度优先搜索 并查集 数组 矩阵 👍 6 👎 0

class MaximumNumberOfFishInAGrid {
    public static void main(String[] args) {
        //创建该题目的对象方便调用

    }
    //leetcode submit region begin(Prohibit modification and deletion)
static class Solution {

    private static final int[][] dirs = {{0,1},{0,-1},{-1,0},{1,0}};
    private int[][] grid;
    public int findMaxFish(int[][] grid) {
        this.grid = grid;

        int n = grid.length;
        int m = grid[0].length;
        int ans = 0;
        for (int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                ans = Math.max(ans,dfs(i,j));
            }
        }
        return ans;
    }

    private int dfs(int i,int j){
        int n = grid.length;
        int m = grid[0].length;

        if(i<0 || i>=n || j<0 || j>=m || grid[i][j] == 0){
            return 0;
        }
        int sum = grid[i][j];
        grid[i][j] = 0;
        for(int[] dir : dirs){
            sum = dfs(i+dir[0],j+dir[j]);
        }

        return sum;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
